<!--
 * @Description: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2022-01-10 08:28:54
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2022-01-10 08:57:54
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>反转指针</title>
</head>

<body>
    <script>
        // 示例: 输入: 1 -> 2 -> 3 -> 4 -> 5 -> NULL 输出: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

        // 思路：改变指针动向即可
        // 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

        // 然后就要开始反转了，首先要把 cur -> next 节点用tmp指针保存一下，也就是保存一下这个节点。

        // 为什么要保存一下这个节点呢，因为接下来要改变 cur -> next 的指向了，将cur -> next 指向pre ，此时已经反转了第一个节点了。

        // 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

        //  最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。


        // 双指针
        var reverseList = function (head) {
            if (!head || !head.next) {
                return head;
            }
            let temp = null, pre = null, cur = head;
            while (cur) {
                temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }



        // 递归法
        var reverse = function (pre, head) {
            if (!head) {
                return pre;
            }
            const temp = head.next;
            head.next = pre;
            pre = head;
            return reverse(pre, head);
        }
        var reverseList = function (head) {
            return reverse(head);
        }



        // 尾部递归
        let reverse = function (head) {
            if (!head || !head.next) {
                return head;
            }
            //从后往前递归
            const pre = reverse(head.next);
            head.next = pre.next;
            pre.next = head;
            return head;
        }
        var reverseList = function (head) {
            let cur = head;
            while (cur && cur.next) {
                cur = cur.next;
            }
            reverse(head);
            return cur;
        }

    </script>
</body>

</html>